[[분류:정보]] ==개요== 이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다. 어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 분석에 관해서는 [[시간 복잡도]] 문서 참고. ==기초적인 정렬 알고리즘== ===선택 정렬(Selection Sort)=== 가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다. ====의사 코드==== 다음은 선택 정렬의 의미를 간이화하여 서술한 코드이다. {{{#!syntax java selectionSort(A[], n): for last ← n-1 downto 1 A[0…last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] }}} 다음은 의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다. {{{#!syntax java selectionSort(A[], n): for last ← n-1 downto 1 k ← theLargest(A, last) tmp ← A[k]; A[k] ← A[last]; A[last] ← tmp theLargest(A[], last): largest ← 0 for i ← 1 to last if (A[i] > A[largest]) largest ← i return largest }}} ====분석==== 의사코드 1을 보자. 선택 정렬의 수행 시간은 모든 경우에 [math(\Theta(n^2))]이다. for 루프는 [math(n-1)]번 순환하고, index 교환은 상수 시간이 든다. 큰 수를 찾는 것은 작업은 부분 배열의 크기에 비례한다.[* 크기가 k인 배열에서 가장 큰 수를 찾는 데는 [math(k-1)]번의 비교가 필요하다.] 부분 배열의 크기는 for문에서 n부터 시작하여 2까지 감소한다. 그러므로 비교하는 총 횟수는 [math((n-1)+(n-2)+…+1=\dfrac{n(n-1)}{2})], 즉 [math(\Theta(n^2))]이다. ===버블 정렬(Bubble Sort)=== 인접한 두 요소를 반복적으로 비교하고, 순서가 맞지 않으면 서로 자리를 바꾸는 방식으로 데이터를 정렬하는 알고리즘이다. ====의사 코드 ==== 다음은 버블 정렬의 의미를 간이화하여 서술한 코드이다. {{{#!syntax java bubbleSort(A[], n): for last ← n-1 downto 1 for i ← 0 to last-1 if (A[i] > A[i+1]) A[i] ↔ A[i+1] }}} 다음은 이미 정렬이 완료된 상태이면 작업을 종료하여 효율을 높인 코드이다. {{{#!syntax java bubbleSort(A[], n): sorted ← FALSE for last ← n-1 downto 1 sorted ← TRUE for i ← 0 to last-1 if (A[i] > A[i+1]) A[i] ↔ A[i+1] sorted ← FALSE if (sorted) return }}} ====분석==== ===삽입 정렬(Insertion Sort)=== 이미 정렬된 부분 데이터에 새로운 데이터를 하나씩 비교하며 올바른 위치에 '삽입'하여 정렬을 완성하는 알고리즘이다. ====의사 코드==== 다음은 삽입 정렬의 의미를 간이화하여 서술한 코드이다. {{{#!syntax java insertionSort(A[], n): for i ← 1 to n-1 A[0…i]의 적합한 자리에 A[i]를 삽입한다. }}} 다음은 재귀를 이용한 코드이다. {{{#!syntax java insertionSort(A[], n): if (n>1) insertionSort(A[], n-1) A[0…n-1]의 적합한 자리에 A[n-1]를 삽입한다. }}} 다음은 적합한 자리를 찾는 로직을 풀어 서술한 코드이다. {{{#!syntax java insertionSort(A[], n): for i ← 1 to n-1 newItem ← A[i] for (j←i-1; 0 ≤ j and newItem < A[j]; j--) A[j] ← A[j+1] A[j+1] ← newItem }}} ====분석==== ==고급 정렬 알고리즘== 전체 리스트를 절반으로 계속 나누어 각 부분을 정렬한 후, 다시 병합하는 분할 정복 기반의 정렬 알고리즘이다. 합병 정렬이라고도 한다. ===병합 정렬(Merge Sort)=== ====의사 코드==== 다음은 병합 정렬의 의미를 간단히 서술한 코드이다. {{{#!syntax java mergeSort(A[], p, r): if (p < r) q ← ⌊(p+r)/2⌋ mergeSort(A, p, q) mergeSort(A, q+1, r) merge(A, p, q, r) merge(A[], p, q, r): 정렬된 두 배열 A[p…q]와 A[q+1…r]을 합쳐 정렬된 하나의 배열 A[p…r]을 만든다. }}} 다음은 병합 함수(merge)를 풀어 서술한 코드이다. {{{#!syntax java merge(A[], p, q, r): i ← p; j ← q+1; t ← 0 while (i ≤ j q and j ≤ r) if (A[i] ≤ A[j]) tmp[t++] ← A[i++] else tmp[t++] ← A[j++] while (i ≤ q) tmp[t++] ← A[i++] while (j ≤ r) tmp[t++] ← A[j++] i ← p; t ← 0 while (i ≤ r) A[i++] ← tmp[t++] }}} ====분석==== 병합 정렬의 수행 시간은 모든 경우에 [math(\Theta(n\log n))]이다. 이 알고리즘은 비교 횟수를 기준으로 수행 시간을 분석해도 되지만 비교 횟수보다 더 잦은 작업이 있다. 바로 원소를 옮기는 작업으로, A[]와 tmp[]를 번갈아 옮기기 때문에 어떤 경우든 [math(2n)]번의 이동이 일어난다. 비교횟수를 기준으로 분석하면 이 때는 [math(2n)] 대신 [math(n/2)] ~ [math(n-1)]이 된다. 점근적 분석 결과는 원소 이동 횟수와 비교 횟수가 동일하지만 시간을 지배하는 작업을 하나 정한다면 이동 횟수가 더 정확한 기준이 된다. 크기가 m인 배열을 병합 정렬로 처리하는 시간을 T(n)이라고 하면 다음과 같다. [math({\rm{T}}(n)=\begin{cases}\displaystyle 1 & \quad (n = 1) \\\displaystyle 2T(\frac{n}{2})+2n &\quad (n > 1) \end{cases} )] [[시간 복잡도#s-3.3|마스터 정리]]을 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다. ===퀵 정렬(Quick Sort)=== 분할 정복 기법을 사용하여 기준값(피벗)을 중심으로 데이터를 작은 값과 큰 값으로 나누고, 이 과정을 재귀적으로 반복하여 매우 빠르게 데이터를 정렬하는 알고리즘이다. ===힙 정렬(Heap Sort)=== 힙 자료구조를 이용해 데이터를 정렬하는 알고리즘으로, 배열을 최대 힙(또는 최소 힙)으로 만든 뒤, 루트(가장 크거나 작은 값)를 배열의 마지막 요소와 교환하고 힙 크기를 줄이는 과정을 반복하는 알고리즘이다. 본 문서에서는 가장 큰 원소 맨 위의 노드에 삽입하는 것을 기준으로 서술한다. ===셸 정렬(Shell Sort)=== 삽입 정렬의 단점을 보완한 알고리즘으로, 처음에는 큰 간격으로 데이터를 나눠 부분 정렬을 하고, 간격을 점점 줄여가며 최종적으로는 전체 데이터를 효율적으로 정렬하는 알고리즘이다.
